package hasWeight;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 使用优先队列，实现prim最小生成树
 */
public class Prim {
    private WeightedGraph graph;
    private List<WeightedEdge> mst;

    public Prim(WeightedGraph g) {
        this.graph = g;
        mst = new ArrayList<>();
        CCollection cc = new CCollection(g);
        if (cc.count() > 1) {
            return;
        }
        //Prim
        boolean[] visited = new boolean[graph.getVertexNum()];
        visited[0] = true;
        Queue pq = new PriorityQueue<WeightedEdge>();
        for (int w : graph.adj(0)) {
            pq.add(new WeightedEdge(0, w, graph.getWeight(0, w)));
        }
        while (!pq.isEmpty()) {
            WeightedEdge minEdge = (WeightedEdge) pq.remove();
            if (visited[minEdge.getV()] && visited[minEdge.getW()]) {
                continue;
            }
            mst.add(minEdge);
            int newv = visited[minEdge.getV()] ? minEdge.getW() : minEdge.getV();
            for (int w : graph.adj(newv)) {
                if (!visited[w]) {
                    pq.add(new WeightedEdge(newv, w, graph.getWeight(newv, w)));
                }
            }
            visited[newv] = true;
        }
    }

    public List<WeightedEdge> result() {
        return mst;
    }

    public static void main(String[] a) {
        WeightedGraph graph = new WeightedGraph("weightedGraph.txt");
        Prim prim = new Prim(graph);
        System.out.println(prim.result());
    }
}
